情報理学I 第2回レポート
tex-button.icon 文字数カウント-button.icon
/icons/hr.icon
情報理学第2回レポート
問1.
4種類の情報源記号{A, B, C, D}が確率的に選択される記憶のない情報源について、 2元ハフマン符号化の方法に従って符号化を行い、各情報源記号に対する符号を 表に示せ。また、符号の木で図示せよ。 https://gyazo.com/e5c7f877506990287a7d7161ae8dc4c9
符号の木
https://gyazo.com/b4cd9638ba2a3138b069133f02bdb3f6
平均符号長$ \bar{L}は
$ \bar{L} = 0.180*3 + 0.250*2 + 0.110*3 + 0.460*1 = 1.83bit
問2.
右の行列は、(7,4)ハミング符号のパリティ検査行列である。「?」を埋めて行列を完成させよ。また、$ H に対する生成行列 $ G を求めよ。 $ H = \begin{pmatrix} ? & ? & 1 & ? & 1 & 0 & 0 \\ ? & ? & 1 & 0 & 0 & 1 & 0 \\ ? & 0 & 1 & ? & 0 & 0 & 1 \end{pmatrix}
n-k ビットのパターンで列ベクトルを作る
3ビットのパターンで列ベクトルを作る(零ベクトルを除く)
(0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0 ,0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
これを当てはめると、
$ H = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}
がパリティ検査行列である.
生成行列は
$ G = \begin{pmatrix} 1&0&0&0& 0&0&1 \\ 0&1&0&0& 1&1&0 \\ 0&0&1&0& 1&1&1 \\ 0&0&0&1& 1&0&1 \end{pmatrix}
受信語として(1,1,0,1,1,1,0)を受け取ったとき、この受信語に1ビットの 誤りが発生しているかどうか検査せよ。もし誤りがある場合は訂正し、 正しい送信語を求めよ。 $ H\begin{pmatrix} 1\\1\\0\\1\\1\\1\\0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1\\1\\0\\1\\1\\1\\0 \end{pmatrix} = \begin{pmatrix}1\\0\\0\end{pmatrix}
より、誤りが発生している。
https://gyazo.com/0690bc9b0298b867a16e3ffa31b4914d
対応するパターンは (0, 0, 0 ,0 ,1, 0, 0) なので送信語は
$ \bm{x} = \bm{y} + \bm{e} = (1, 1, 0, 1, 0, 1, 0)
/icons/hr.icon
Terms
問1
問2